package com.faiz.algorithm;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class Solution {
    public static boolean validateStackSequences(int[] pushed, int[] popped) {
        boolean result = true;
        int length = pushed.length;
        if (length == 0) {
            return true;
        }
        Deque<Integer> stack = new LinkedList<>();
//        stack.push(Integer.valueOf(pushed[0]));
        int j = 0;
        for (int i = 0; i < length; i++) {
            if (stack.peek() == null) {
                stack.push(Integer.valueOf(pushed[i]));
                j++;
            }
            if (stack.peek() == popped[i]) {
                stack.pop();
            } else {
                if (j >= length) {
                    result = false;
                    break;
                }
                while (j < length && pushed[j] != popped[i]) {
                    stack.push(Integer.valueOf(pushed[j]));
                    j++;
                }
                j++;
            }
        }
        return result;
    }
}